package com.lwl.leetcode;

/**
 * @author lwl
 * @Description 给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: data = [1,0,1,0,1]
 * 输出: 1
 * 解释:
 * 有三种可能的方法可以把所有的 1 组合在一起：
 * [1,1,1,0,0]，交换 1 次；
 * [0,1,1,1,0]，交换 2 次；
 * [0,0,1,1,1]，交换 1 次。
 * 所以最少的交换次数为 1。
 * @date 2025/9/5 17:53
 */
public class Code1151MinSwaps {

    public static void main(String[] args) {
        int[] data = {
                1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1
        };
        System.out.println(minSwaps(data));
    }
    public static int minSwaps(int[] data) {
        // 使用一个窗口（大小为1的个数），查看窗口可以扩住最多1的情况，剩下的0替换为1
        int windows = 0;
        for (int i = 0; i < data.length; i++) {
            if (data[i] == 1) {
                windows++;
            }
        }
        int left = 0;
        int curOneNumber = 0;
        int res = 0;
        for (int right = 0; right < data.length; right++) {
            while (right - left >= windows) {
                curOneNumber -= data[left++];
            }
            curOneNumber += data[right];
            if (right - left + 1 == windows) {
                res = Math.max(res, curOneNumber);
            }
        }
        return windows - res;
    }
}
